package 剑指offer_专项突击版.中等;

import 分类.前缀和;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入: nums = [0,1]
 * 输出: 2
 * 说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
 * 示例 2：
 * <p>
 * 输入: nums = [0,1,0]
 * 输出: 2
 * 说明: [0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/A1NYOS
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author caihe
 * @date 2022/11/4 13:41
 */
public class _011_0和1个数相同的子数组 implements 前缀和 {
    public static void main(String[] args) {
        _011_0和1个数相同的子数组 a = new _011_0和1个数相同的子数组();
        a.findMaxLength(new int[]{0, 0, 0, 1, 1, 1});

    }

    /**
     * 需要找到这个数组中0和1出现数量一致的子数组
     * 则可以设 遇到0的时候 前缀和减一  遇到1的时候前缀和加一
     * 当0和1数量一致时 前缀和为0
     */
    public int findMaxLength(int[] nums) {
        
        // 使用前缀和进行处理和记录
        Map<Integer, Integer> map = new HashMap<>();
        // key代表前缀和 value代表下标  
        map.put(0, -1);
        int preNum = 0, res = 0;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            // 如果当前的元素为1 则
            if (num == 1) {
                preNum += 1;
            } else {
                preNum += -1;
            }
            // 存在相同的前缀和 说明遇到数量相同的0和1
            if (map.containsKey(preNum)) {
                // 获取对应的相反的下标
                Integer index = map.get(preNum);
                res = Math.max(res, i - index);
            } else {
                map.put(preNum, i);
            }             
        }
        return res;
    }

}
